Skip to main content

Zero-Knowledge and MPC

Overview​

Zero-knowledge proofs are a cryptographic technique that allows a user (the prover) to demonstrate the validity of a statement to another party (the verifier) without revealing any underlying information other than the fact that the statement is true. The technique offers privacy and security by concealing sensitive information while preserving the ability to verify and establish trust. The following three properties are typically satisfied in a zero-knowledge protocol:

  • Completeness: When the statement is true and both parties adhere to the protocol honestly, the verifier will be convinced of its truth.

  • Soundness: When the statement is false, a malicious prover cannot persuade the verifier otherwise, except with negligible probability.

  • Zero-Knowledge: The verifier does not learn anything regarding the underlying details of the statement except its validity, maintaining the prover's confidentiality.

This technique is widely applied in privacy-enhancing authentication use cases, such as secure identity verification, blockchain transactions, and cryptographic protocols like zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) and zk-STARKSs (Zero-Knowledge Scalable Transparent Arguments of Knowledge). With zero-knowledge proofs, users can, for example, prove ownership of a private key or correctness of a computation without divulging the key or the data itself, making it a cornerstone of modern privacy-focused cryptography.

Zero-Knowledge and MPC Wallets​

In Multi-Party Computation (MPC) wallets, the private key is fragmented and shared between multiple parties (e.g., the user, a server, or other co-participants). Zero-Knowledge Proofs (ZKPs) can be utilized to demonstrate that such fragments have been created correctly or that processes, such as transaction signing, have been executed correctly, without revealing the key fragments themselves. Before an MPC protocol for transaction signing is initiated, ZKPs can be utilized to validate that all inputs (e.g., transaction data, amount, and address) are correct and in line with the rules, without disclosing specific information regarding these inputs. In blockchains, ZKPs can be utilized to conceal transaction data (e.g., amount, sender, and recipient), while MPC enables several parties to co-sign a transaction without exposing the entire private key. This is particularly helpful to ensure privacy in financial applications. Since no single party holds the full private key, and ZKPs also ensure that no sensitive information is revealed in the process, the risk of key theft or misuse is significantly reduced.

Benefits​

  • Privacy: Key and transaction information is maintained confidential.

  • Security: Key distribution and ZKPs minimize the risk of compromise.

  • Flexibility: Can be used in a broad variety of blockchain systems and use cases, including DeFi, healthcare, and identity management.

Challenges​

  • Complexity: Both MPC and ZKPs take substantial computational time and resources to carry out.

  • Scalability: It is still a challenge to scale to large systems.

  • Expertise: These solutions need to be implemented and designed by those with a good background in cryptography.

Figure1: Use of zero knowledge. Source:https://medium.com

Zero-Knowledge Proofs in ECDSA based TSS Algorithms​

Recent advancements in zero-knowledge proof (ZKP) technologies have led to the development of more efficient threshold signature schemes (TSS), which are increasingly used in multi-signature wallet implementations within the blockchain ecosystem. The following section explores how zero-knowledge methods are integrated into leading TSS algorithms based on the Elliptic Curve Digital Signature Algorithm (ECDSA).

1. Lindell17​

Zero-knowledge proofs (ZKPs) are integrated throughout the algorithm to ensure that all parties behave honestly and that cryptographic operations are performed correctly. Specifically, they verify the integrity of commitments and exponentiations, the correctness of Paillier key generation and related operations, and the consistency of share multiplications. Early in the protocol, participants provide ZKPs demonstrating knowledge of the discrete logarithms underlying the Pedersen commitments they exchange. This allows them to prove possession of the committed values without revealing the actual data. The party responsible for generating the Paillier keypair also provides zero-knowledge proofs showing that the Paillier modulus is the product of two safe primes, which confirms the key is well-formed. In addition, they must prove that the encrypted secret shares are valid and that the corresponding plaintexts are both small and correct. As the protocol proceeds, participants prove knowledge of the discrete logarithms corresponding to committed nonce shares. Additional proofs verify that the exponents used in scalar multiplications or ciphertext exponentiations match the committed values. These ZKPs also confirm that product commitments align with their respective input commitments, ensuring the correctness of the multiplications. Finally, consistency is checked across Paillier ciphertexts, Pedersen commitments, and ElGamal encryptions of the same secrets to guarantee coherence and prevent malicious behavior.

Zero-Knowledge & Proofs ZK proofs are inserted throughout this algorithm to ensure:

  • Commitments and exponentiations are honest.
  • Paillier keys and operations are correct.
  • Multiplications in shares are consistent.

2. GG18​

Zero-knowledge proofs (ZKPs) are integrated into several parts of the algorithm to ensure robustness against malicious behavior and to maintain the integrity of the protocol. First, each participant must demonstrate, in zero-knowledge, that their commitments were constructed correctly. This involves proving that they possess the underlying polynomial coefficients and the randomness used to generate the commitments, without revealing this information. Later in the protocol, participants are required to prove that their ciphertexts encrypt values within the correct range. This step ensures that no malformed ciphertexts are introduced, which could otherwise be used to mount attacks. Additionally, each party must provide a zero-knowledge proof that they correctly computed the encrypted product using their private input. This is achieved through a zero-knowledge proof of correct multiplication (ZK-MtA). Optionally, participants may also provide a discrete logarithm equality (DLEQ) proof to show that their public nonce commitment corresponds to their actual secret nonce share, which helps prevent dishonest claims about nonce values.

3. GG20​

GG18’s zero-knowledge proofs are simpler and less integrated, primarily focusing on proving the correctness of encrypted data without guaranteeing protection against malicious behavior. In contrast, GG20 introduces a comprehensive suite of efficient, modular, and aggregated zero-knowledge proofs that enable secure, fault-tolerant multiparty signing with provable identification of cheating parties and allow the protocol to continue after their exclusion.

Projects Utilizing Zero-Knowledge Proofs​

Zero-knowledge proofs (ZKPs) enable privacy-preserving verification in cryptographic systems, where users can demonstrate knowledge or ownership without revealing sensitive details. We consider two such prominent projects, Ledger and Tornado Cash that leverage ZKPs along with associated cryptographic primitives, such as Shamir's Secret Sharing (SSS), Verifiable Secret Sharing (VSS), Distributed Key Generation (DKG), and Threshold Signature Schemes (TSS), to achieve security and privacy.

Ledger Cold Wallet​

Ledger, a well-known hardware wallet vendor, employs a sophisticated key management system to secure users' private keys while incorporating recovery mechanisms. The system utilizes zero-knowledge proofs to offer key security from theft and to ensure control for the user.

  • Key Structure: The private key is split into three shares using Shamir's Secret Sharing (SSS). The user holds one share and Ledger holds the other two. Two shares are required as a threshold to sign a transaction, so the user's share alone is insufficient, but any two shares (e.g., the user's and one of Ledger's) can authorize a signature.

  • Recovery Mechanism: If the user loses his share, recovery is possible with the two shares with Ledger. It employs Distributed Key Generation (DKG) to ensure that the key is never complete during creation and recovery, and Verifiable Secret Sharing (VSS) for checking the integrity of the shares without disclosing them.

  • Threshold Signing: The network makes use of an ECDSA-based Threshold Signature Scheme (TSS) that allows signing a transaction with only a subset of the key shares (e.g., 2 of 3). Zero-knowledge proofs are used within the signing protocol to render it impossible for an attacker to steal a share by requiring participants to prove knowledge of the share without revealing it.

  • Security Issues with Paillier Encryption: Ledger’s TSS implementation uses Paillier homomorphic encryption, as seen in protocols such as GG18 and GG20. However, there is a critical weakness when the ciphertext is larger than the public key modulus, which enables an attacker to obtain the private key via a large-number attack. To mitigate this, zero-knowledge range proofs maintain the encrypted values within secure ranges, a lesson learned from vulnerabilities found in protocols like Lindell17 (e.g., Fireblocks' study on broken implementations).

With the composition of SSS, VSS, DKG, TSS, and ZKPs, Ledger maintains the private key secure, distributed, and recoverable, and zero-knowledge mechanisms protect against unwanted access attempts.

Tornado Cash​

Tornado Cash is a decentralized, non-custodial privacy solution on Ethereum that uses zero-knowledge proofs to enable anonymous transactions. It uses zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) and an incremental Merkle tree to obfuscate transaction data without preventing verifiability.

  • Deposit Process: Deposits are made by users in discrete denominations of ETH (i.e., 0.1, 1, 10, or 100 ETH), similar to our predefined "denominations" concept. This restriction simplifies privacy enforcement. A cryptographic commitment (a hash) is added as a leaf to a growing on-chain Merkle tree at deposit.

  • Incremental Merkle Tree: It is a binary tree that efficiently represents transaction history. Leaves are commitments, and higher nodes merge hashes for quick integrity auditing. Updates are quick and inexpensive despite the large number of transactions. Tornado Cash stores the history of the last 30 Merkle roots, which are snapshots of the tree's state over time.

  • Withdrawal Process: To withdraw funds, users must generate a zk-SNARK proof of ownership of a committed deposit (i.e., knowledge of the preimage of the hash) without explicitly divulging the preimage. The proof corresponds to one of the Merkle roots in the tree's history, attesting to the user's funds being in the pool without announcing their identity or deposit details. Optionally, relayers third-party services may submit the proof on behalf of users, enabling minimal interaction with the blockchain by the users.

  • Privacy Layer: Tornado Cash transfers the funds to a new address after confirmation, breaking the link between the deposit and the withdrawal. Zero-knowledge proof enables users to call the preimage of a hash (prove knowledge of the secret input) without divulging it, allowing high privacy for financial transactions.

  • Implementation Details: Tornado Cash leverages zk-SNARKs for shrinking complex proofs into succinct, verifiable representations, and the incremental Merkle tree for on-chain data optimization. The design ensures low transaction costs and scalability even when the pool grows in size.

Tornado Cash is an excellent illustration of how ZKPs, when combined with Merkle tree constructions, can provide an efficient privacy solution that enables users to transact safely without revealing sensitive details.

Both Ledger and Tornado Cash demonstrate the power of zero-knowledge proofs in enhancing security and privacy. Ledger uses ZKPs in a TSS framework (founded on SSS, VSS, and DKG) to protect a three-part key system, with the objective of secure signing and recovery and defense against attacks like those exploiting Paillier encryption vulnerabilities. Tornado Cash employs zk-SNARKs and an incremental Merkle tree to make transactions anonymous so that users can provide proof of funds without compromising privacy. These projects highlight the versatility of ZKPs in addressing practical cryptographic issues, from wallet security to financial anonymity.

Summary​

These TSS algorithms Lindell17, GG18, and GG20 demonstrate the evolution of zero-knowledge techniques in ECDSA-based threshold schemes. Lindell17 is the most efficient two-party solution with fast signing but must be carefully implemented to avoid vulnerability. GG18 provides a secure multiparty computation protocol at the expense of efficiency, and GG20 achieves a trade-off between security, efficiency, and accountability, which is a more desirable protocol for modern blockchain multi-signature wallets. They are all derived from zero-knowledge proofs to protect key shares and ensure privacy, and recent advances have made them much more feasible for engineering deployment. Zero-knowledge proofs and MPC wallets are complementary tools that enhance security and privacy in distributed systems. Zero-knowledge proofs ensure validation without revealing data, while MPC enables secure collaboration among multiple parties. In MPC wallets, zero-knowledge proofs can strengthen processes like signing or authentication, making them ideal for systems requiring high levels of privacy and security.